
/*
Description:
Given n non-negative integers a1, a2, ..., an , where each represents a point at coordinate (i, ai). 
n vertical lines are drawn such that the two endpoints of line i is at (i, ai) and (i, 0). 
Find two lines, which together with x-axis forms a container, such that the container contains the most water.

Note: You may not slant the container and n is at least 2.

Example:

Input: [1,8,6,2,5,4,8,3,7]
Output: 49
*/

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

using namespace std;


/**
* Definition for a binary tree node.
*/

class Solution {
public:
	int maxArea(vector<int>& height) {
		int area = 0;
		int tmp = 0;
		int len = height.size();
		int x1, x2;
		for (x1 = 1, x2 = len; x1 < x2;)
		{
			tmp = (x2 - x1) * std::min(height[x1 - 1], height[x2 - 1]);
			if (tmp > area)
			{
				area = tmp;				
			}
			if (height[x1 - 1]< height[x2 - 1])
			{
				x1++;
				cout << area << " " << x1 << " " << x2 << endl;
			}
			else
			{
				x2--;
				cout << area << " " << x1 << " " << x2 << endl;
			}
		}
		return area;
	}
	int maxArea0(vector<int>& height) {
		int area = 0;
		int tmp = 0;
		int len = height.size();
		for (int x = 1; x < len; x++)
		{
			for (int x2 = x + 1; x2 <= len; x2++)
			{				
				tmp = (x2 - x) * std::min(height[x - 1], height[x2 - 1]);
				if (tmp > area)
				{
					area = tmp;
					//cout <<area<<" "<<  x << " " << x2 << endl;
				}
			}
		}		

		return area;
	}
};

int _maxArea()
{
	vector<int> h1 { 1,8,6,2,5,4,8,3,7 };
	vector<int> h2{ 2,3,4,5,18,17,6 };

	vector<int> height(h2);
	Solution solu;
	int area;

	area = solu.maxArea0(height);

	cout << "heights: " <<  endl;
	for(int h:height)
	{
		cout << h << " ";
	}
	cout << endl;
	cout << "maxArea: " << area << endl;

	return 0;
}

